#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>

using namespace std;
int bfs(string begin, string end, vector<string>& word);

int ladderLength(string beginWord, string endWord, vector<string>& wordList)
{
    int ret = bfs(beginWord, endWord, wordList);
    return ret;
}

int bfs(string begin, string end, vector<string>& word)
{
    unordered_map<string, int> hash1;
    unordered_map<string, int> hash2;
    int count = 0;
    char arr = 'a';
    queue<string> q;
    hash1[begin]++;
    for (auto& e : word)
    {
        hash2[e]++;
    }
    if (hash2.count(end) == 0)
    {
        return 0;
    }
    q.push(begin);
    while (q.size())
    {
        int sz = q.size();
        int tag = 0;
        for (int i = 0; i < sz; i++)
        {
            string s = q.front();
            q.pop();
            for (int m = 0; m < begin.size(); m++)
            {
                for (int n = 0; n < 26; n++)
                {
                    string temp = s;
                    temp[m] = arr + n;
                    if (hash2.count(temp) == 1)
                    {
                        if (hash1.count(temp) == 0)
                        {
                            hash1[temp]++;
                            q.push(temp);
                            if (tag == 0)
                            {
                                count++;
                            }
                            tag = 1;
                        }

                    }
                    if (temp == end)
                    {
                        return count + 1;
                    }
                }
            }
        }
    }
    return 0;
}


int main()
{
    string beginWord = "hot";
    string endWord = "dog";
    vector<string> wordList = { "hot","dog" };
    bfs(beginWord, endWord, wordList);
    return 0;
}